//希尔排序是直接插入排序的改进算法

#include <iostream>

using namespace std;

/**
    设置不同的间隔，按照间隔找到分组
    1，2，3，4，5==>设置2为间隔，那么1，3，5是一组，2，4是一组。
*/

int shellSort(int arr[], int n)
{
    if(arr==NULL||n==0)
    {
        return 0;
    }
    //进行几趟排序
    int num = n;
    int flag = 0;
    while(num>0)
    {
        num = num/2;  //每次取上一次的半数
        //改进的冒泡法对子序列排序
        do{
            flag = 0;
            for(int i = 0;i<n-num;i++)
            {
                int j = i+num;
                if(arr[i]>arr[j])
                {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    flag = 1; //如果有交换就继续循环，没有交换就下一趟排序
                }
            }
        }while(flag);


    }
    return 1;
}
int main()
{

    int arr[] = {5,30,7,9,20,10};
    shellSort(arr,6);
    for(int i = 0;i<6;i++)
    {
        cout<<arr[i]<<",";
    }
    system("pause");
    return 0;
}
